package com.taldh.algorithm.array;

import org.junit.Assert;
import org.junit.Test;

public class TrapSolution {
    /**
     * 42. 接雨水
     *
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int ans = 0;

        int len = height.length;
        for (int i = 0; i < len - 1; i++) {
            if (height[i] == 0) {
                continue;
            }
            if (height[i] <= height[i+1]){
                continue;
            }
            int firstGreater = getFirstGreater(height, i);
            if (firstGreater == -1) {
                int secGreater = getSecondGreater(height, i);
                ans += getArea(height, i, secGreater);
                i = secGreater - 1;
                continue;
            }
            ans += getArea(height,i, firstGreater);
            i = firstGreater - 1;
        }

        return ans;
    }

    private int getSecondGreater(int[] height, int index) {
        int len = height.length;
        int secIndex = -1;
        int secMax = -1;
        for (int i = index + 1; i < len ; i++) {
            if (secMax <= height[i]) {
                secMax = height[i];
                secIndex = i;
            }
        }
        return secIndex;
    }

    private int getArea(int[] height, int i, int firstGreater) {
        int area = Math.min(height[i], height[firstGreater]) * (firstGreater - i - 1);
        for (int j = i + 1; j < firstGreater ; j++) {
            area -= height[j];
        }
        return area;
    }

    private int getFirstGreater(int[] height, int index) {
        int len = height.length;
        if (index == len - 1) {
            return -1;
        }
        for (int i = index + 1; i < len ; i++) {
            if (height[i] >= height[index]) {
                return i;
            }
        }
        return -1;
    }

    @Test
    public void test1() {
        Assert.assertEquals(6, trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

    @Test
    public void test2() {
        Assert.assertEquals(1, trap(new int[]{4,2,3}));
    }

    @Test
    public void test3() {
        Assert.assertEquals(1, trap(new int[]{5,4,1,2}));
    }


}